package C057;

import java.util.Arrays;

/**
 * ClassName: c04
 * Package: C057
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/5/2 12:39
 * @Version 1.0
 * @Since 1.0
 */
public class c04 {
    public static void main(String[] args) {
        //int[][] arr = {{1,1,0},{1,1,0},{0,0,1}};
        //int[][] arr = {{1,1,0,0},{1,1,1,0},{0,1,1,1},{0,0,1,1}};
        int[][] arr = {{1,0,0,0,0,1,0},{0,1,1,0,0,0,0},{0,1,1,0,0,0,0},{0,0,0,1,0,0,0},{0,0,0,0,1,0,0},{1,0,0,0,0,1,0},{0,0,0,0,0,0,1}};
        int[] arr2 = {4};
        System.out.println(minMalwareSpread(arr, arr2));
    }

    static int MAXLEN = 301;
    static int[] father = new int[MAXLEN];
    static int[] size = new int[MAXLEN];

    /*
    感染源i拯救的节点个数
     */
    static int[] cnts = new int[MAXLEN];

    /*
    是否是感染源, 方便查询
     */
    static boolean[] virus = new boolean[MAXLEN];

    /*
    -1 表示没有感染
    > 0 感染其的源头是 infect[i]
    -2 多个感染源
     */
    static int[] infect = new int[MAXLEN];

    public static int minMalwareSpread(int[][] graph, int[] initial) {
        build(graph.length, initial);

        // 合并非感染源的节点
        for (int i = 0; i < graph.length; i++) {
            for (int j = i; j < graph[0].length; j++) {
                if (!virus[i] && !virus[j] && graph[i][j] == 1) {
                    union(i, j);
                }
            }
        }

        // 感染源邻居统计, 遍历感染源的邻接矩阵
        for (int i : initial) {
            for (int j = 0; j < graph[0].length; j++) {
                if (j != i && !virus[j] && graph[i][j] == 1 && infect[j] != -2) {
                    int fn = find(j);
                    if (infect[fn] == -1) {
                        infect[fn] = i;
                    } else if (infect[fn] != i) {
                        infect[fn] = -2;
                    }
                }
            }
        }

        // 统计个数
        for (int i = 0; i < graph.length; i++) {
            if(i == find(i) && infect[i] >= 0 && !virus[i]) {
                 cnts[infect[i]] += size[i];
            }
        }

        // 返回最大的拯救数的节点下标
        Arrays.sort(initial);
        int max = -1, index = 0;
        for (int i : initial) {
            if(cnts[i] > max) {
                index = i;
                max = cnts[i];
            }
        }
        return index;
    }

    // 合并元素
    private static void union(int i, int j) {
        int fi = find(i);
        int fj = find(j);
        if (fi == fj) {
            return;
        }
        father[fi] = fj;
        size[fj] += size[fi];
    }

    // 查找元素
    private static int find(int i) {
        if (i != father[i]) {
            father[i] = find(father[i]);
        }
        return father[i];
    }

    private static void build(int length, int[] initial) {
        Arrays.fill(virus, false);
        for (int i = 0; i < length; i++) {
            virus[i] = false;
            cnts[i] = 0;
            infect[i] = -1;
            size[i] = 1;
            father[i] = i;
        }
        for (int i : initial) {
            virus[i] = true;
        }
    }
}
